package com.hyb.algorithm.data.struct.tree;

/**
 *   450. 删除二叉搜索树中的节点
 *   https://leetcode.cn/problems/delete-node-in-a-bst/description/
 *
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 *
 * @author: ybhu
 * @create: 2023/12/24 22:09
 */
public class DeleteNode2 {


    public TreeNode deleteNode(TreeNode root, int key) {

        if(root==null){
            return null;
        }

        if(root.val<key){
            root.right=deleteNode(root.right ,key);
            return root;
        }

        if(root.val>key){
            root.left=deleteNode(root.left,key);
            return root;
        }

        //如果找到该节点 删除该节点
        if(root.val==key){
            //如果是叶子节点
            if(root.left==null&&root.right==null){
                root=null;
                return null;
            }

            //如果只有左子树
            if(root.right==null){
                return root.left;
            }
            //如果只有右子树
            if(root.left==null){
                return root.right;
            }

            //如果左右子树都不为空  需要找到中继节点，右边最小
            TreeNode successor=root.right;

            while(successor.left!=null){
                successor=successor.left;
            }

            //需要删除掉原来的中继节点, 所以key 为  中继节点的val
            root.right=deleteNode(root.right,successor.val);

            //中继节点替换当前节点的位置 ，左子树替换左子树，右子树替换右子树
            successor.left=root.left;
            successor.right=root.right;

            return successor;

        }

        return null;

    }

}
